#include<iostream>
#include <vector>
#include <assert.h>
#include <math.h>
using namespace std;
struct ListNode {
     int val;
    ListNode *next;
     ListNode() : val(0), next(nullptr) {}
     ListNode(int x) : val(x), next(nullptr) {}
     ListNode(int x, ListNode *next) : val(x), next(next) {}
 };
 
 
   struct TreeNode {
       int val;
       TreeNode *left;
       TreeNode *right;
       TreeNode() : val(0), left(nullptr), right(nullptr) {}
       TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
       TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
   };
  
class Solution {
public:
    void reol(TreeNode* parent, vector<TreeNode*>& s)
    {
        TreeNode* sub = parent->right;
        TreeNode* subl = sub->left;
        size_t i = 0;
        for (i = 0; i < s.size(); i++)
        {
            if (s[i] == parent)
                break;
        }
        if (_root == parent)
        {
            _root = sub;
            sub->left = parent;
            parent->right = subl;
        }
        else
        {
            TreeNode* pparent = s[i - 1];
            if (pparent->left == parent)
                pparent->left = sub;
            else
                pparent->right = sub;
            sub->left = parent;
            parent->right = subl;
        }
    }
    void reor(TreeNode* parent, vector<TreeNode*>& s)
    {
        TreeNode* sub = parent->left;
        TreeNode* subr = sub->right;
        size_t i = 0;
        for (i = 0; i < s.size(); i++)
        {
            if (s[i] == parent)
                break;
        }
        if (_root == parent)
        {
            _root = sub;
            sub->right = parent;
            parent->left = subr;
        }
        else
        {
            TreeNode* pparent = s[i - 1];
            if (pparent->left == parent)
                pparent->left = sub;
            else
                pparent->right = sub;
            sub->right = parent;
            parent->left = subr;
        }
    }
    bool creat(const int& x)
    {
        if (_root == nullptr)
        {
            _root = new TreeNode(x);
            return true;
        }
        vector<TreeNode*> s;
        TreeNode* parent = nullptr;
        TreeNode* cur = _root;
        while (cur)
        {
            parent = cur;
            if (x > cur->val)
                cur = cur->right;
            else if (x < cur->val)
                cur = cur->left;
            else
                return false;
            s.push_back(parent);
        }
        cur = new TreeNode(x);
        if (x < parent->val)
            parent->left = cur;
        else
            parent->right = cur;
        size_t ret = s.size() - 1;
        while (ret >= 0)
        {
            if (abs(bf(parent)) == 0)
                break;
            else if (abs(bf(parent)) == 1)
            {
                cur = parent;
                if (ret != 0)
                    parent = s[--ret];
                else
                    break;
            }
            else if (abs(bf(parent)) == 2)
            {
                if (bf(parent) == 2 && bf(cur) == 1)
                    reol(parent, s);
                else if (bf(parent) == 2 && bf(cur) == -1)
                {
                    reor(cur, s);
                    reol(parent, s);
                }
                else if (bf(parent) == -2 && bf(cur) == -1)
                    reor(parent, s);
                else if (bf(parent) == -2 && bf(cur) == 1)
                {
                    reol(cur, s);
                    reor(parent, s);
                }
                break;
            }
            else
                assert(false);
        }
        return true;
    }
    int high(TreeNode* root)
    {
        if (root == nullptr)
            return 0;
        int left = high(root->left);
        int right = high(root->right);
        return left > right ? left + 1 : right + 1;
    }
    int bf(TreeNode* root)
    {
        if (root == nullptr)
            return 0;
        int left = high(root->left);
        int right = high(root->right);
        return right - left;
    }
    TreeNode* sortedListToBST(ListNode* head)
    {
        if (head == nullptr)
            return nullptr;
        vector<int> v;
        while (head)
        {
            v.push_back(head->val);
            head = head->next;
        }
        for (auto e : v)
        {
             if (creat(e));
            else
                assert(false);
        }
        return _root;
    }
private:
    TreeNode* _root = nullptr;
};
int main()
{
    ListNode* head = nullptr;
    head = new ListNode(0);
    head->next = new ListNode(1);
    head->next->next = new ListNode(2);
    head->next->next->next = new ListNode(3);
    head->next->next->next->next = new ListNode(4);
    head->next->next->next->next->next = new ListNode(5);
    head->next->next->next->next->next->next = new ListNode(6);
    head->next->next->next->next->next->next->next = new ListNode(7);
    head->next->next->next->next->next->next->next->next = new ListNode(8);
    head->next->next->next->next->next->next->next->next->next = new ListNode(9);

    TreeNode* root= Solution().sortedListToBST(head);




    return 0;
}
